12317 - Document Compression/12317.4.cpp

   1 // Equipo Poncho, Carriel y Ruana
   2 // Accepted on UVa - This is the fastest implementation I could get.
   3 using namespace std;
   4 #include <algorithm>
   5 #include <iostream>
   6 #include <iterator>
   7 #include <sstream>
   8 #include <fstream>
   9 #include <cassert>
  10 #include <climits>
  11 #include <cstdlib>
  12 #include <cstring>
  13 #include <string>
  14 #include <cstdio>
  15 #include <vector>
  16 #include <cmath>
  17 #include <queue>
  18 #include <stack>
  19 #include <list>
  20 #include <map>
  21 #include <set>
  22
  23 template <class T> string toStr(const T &x)
  24 { stringstream s; s << x; return s.str(); }
  25 template <class T> int toInt(const T &x)
  26 { stringstream s; s << x; int r; s >> r; return r; }
  27
  28 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  29 #define foreach(x, v) for (typeof (v).begin() x = (v).begin(); x != (v).end(); ++x)
  30 #define D(x) cout << #x " = " << (x) << endl;
  31
  32 const double EPS = 1e-9;
  33
  34 int cmp(double x, double y = 0, double tol = EPS) {
  35     return (x <= y + tol) ? (x + tol < y) ? -1 : 0 : 1;
  36 }
  37
  38 namespace IO {
  39 #define MAXBUFF (1<<18)
  40    char buffer[MAXBUFF], *p = buffer+MAXBUFF;
  41    char buffer2[MAXBUFF], *p2 = buffer2;
  42
  43    inline char read_char() {
  44       if( p == buffer+MAXBUFF ) {
  45          fread( buffer, 1, MAXBUFF, stdin );
  46          p = buffer;
  47       }
  48       return *p++;
  49    }
  50
  51    inline int read_int() {
  52       char c;
  53       while( !isdigit(c = read_char()) );
  54       int ret = c-'0';
  55       while( isdigit(c = read_char()) ) ret = ret * 10 + c-'0';
  56       return ret;
  57    }
  58
  59    void flush() {
  60       fwrite( buffer2, 1, p2-buffer2, stdout );
  61       p2 = buffer2;
  62    }
  63
  64    inline void write( char c ) {
  65       if( p2 == buffer2+MAXBUFF ) {
  66          fwrite( buffer2, 1, MAXBUFF, stdout );
  67          p2 = buffer2;
  68       }
  69       *p2++ = c;
  70    }
  71 }
  72
  73
  74 const int MAXBASES = 105, oo = 1 << 28;
  75 int bases[MAXBASES];
  76
  77 int B, D;
  78 int dp[1 << 16];
  79
  80 void precompute(){
  81     for (int mask = 0; mask < (1 << 16); ++mask) {
  82         dp[mask] = oo;
  83     }
  84     dp[0] = 0;
  85
  86     for (int i = 0; i < B; ++i) {
  87         for (int mask = 0; mask < (1 << 16); ++mask) {
  88             if (dp[mask] >= oo) continue;
  89             int new_mask = mask | bases[i];
  90             int score = dp[mask] + 1;
  91             if (score < dp[new_mask]) dp[new_mask] = score;
  92         }
  93     }
  94 }
  95
  96 int main(){
  97     while (true) {
  98         B = IO::read_int();
  99         D = IO::read_int();
 100         if (B == 0 and D == 0) break;
 101         for (int i = 0; i < B; ++i) {
 102             bases[i] = 0;
 103
 104             int k = IO::read_int();
 105             while (k--) {
 106                 int x = IO::read_int(); x--;
 107                 bases[i] |= (1 << x);
 108             }
 109         }
 110         precompute();
 111         for (int j = 0; j < D; ++j) {
 112             int doc = 0;
 113             int k = IO::read_int();
 114             while (k--) {
 115                 int x = IO::read_int(); x--;
 116                 doc |= (1 << x);
 117             }
 118
 119             int ans = dp[doc];
 120             if (ans >= oo) ans = 0;
 121             printf("%d", ans);
 122
 123             if (j + 1 < D) printf(" ");
 124         }
 125         puts("");
 126     }
 127     return 0;
 128 }